package first.codeTop.alibaba;

/**
 * @ClassName LC23
 * @description:
 * @author: 荣燊
 * @create: 2021-10-14 20:57
 **/
public class LC23 {
    // 合并k个排序列表
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(1);
        node1.next.next = new ListNode(2);
        node1.next.next.next = new ListNode(3);
        node1.next.next.next.next = new ListNode(8);

        ListNode node2 = new ListNode(1);
        node2.next = new ListNode(2);
        node2.next.next = new ListNode(3);
        node2.next.next.next = new ListNode(6);

        ListNode merge = merge(node1, node2);
        while (merge != null) {
            System.out.println(merge.val);
            merge = merge.next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        ListNode temp = merge(lists[0], lists[1]);
        for (int i=2; i<lists.length; i++) {
            temp = merge(lists[i], temp);
        }
        return temp;

    }

    public static ListNode merge(ListNode node1, ListNode node2) {
//        if (node1 == null) {
//            return node2;
//        }
//        if (node2 == null) {
//            return node1;
//        }
        ListNode listNode = new ListNode();
        ListNode root = listNode;
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                listNode.next = node1;
                node1 = node1.next;
            } else {
                listNode.next = node2;
                node2 = node2.next;
            }
            listNode = listNode.next;
        }
        if (node1 == null) {
            listNode.next = node2;
        }
        if (node2 == null) {
            listNode.next = node1;
        }
        return root.next;
    }

    // 还可以使用分治法

}
